package com.gitee.feizns.explore.data_structure.linked_list.singly.sort;

import com.gitee.feizns.explore.data_structure.linked_list.singly.ListNode;

/**
 * @author feizns
 * @since 2020/3/3
 */
public class SortList {

    private static ListNode create() {
        ListNode r = new ListNode(5);
        r.next = new ListNode(4);
        r.next.next = new ListNode(3);
        r.next.next.next = new ListNode(2);
        r.next.next.next.next = new ListNode(1);
        return r;
    }

    private static void println(ListNode n) {
        ListNode t = n;
        while ( t != null ) {
            System.out.print(t.val);
            t = t.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ListNode node = new SortList().sortList(create());
        println(node);
    }

    public ListNode sortList(ListNode head) {
        ListNode pre = new ListNode(-1);
        pre.next = head;
        int len = len(head);
        for (int i = 1; i < len; i+=i) {
            ListNode p = pre;
            ListNode last;
            while ((last = sort(p, i)) != null ) {
                p = last;
            }
        }
        return pre.next;
    }

    private ListNode sort(ListNode pre, int l) {
        if ( pre.next == null ) return null;
        ListNode fast = pre;
        ListNode slow = fast;
        int i = 0;
        for (; fast.next != null && i < l; i++) {
            fast = fast.next;
            slow = slow.next;
            if ( fast.next != null )
                fast = fast.next;
        }
        while ( slow.next != null && i++ < l ) {
            slow = slow.next;
        }
        if ( slow != pre ) {
            ListNode fastNext = fast.next;
            fast.next = null;
            ListNode tmp = slow.next;
            slow.next = null;
            pre.next = merge(pre.next, tmp);
            ListNode last = pre.next;
            while ( last.next != null )
                last = last.next;
            last.next = fastNext;
            return last;
        }
        return null;
    }

    private static ListNode merge(ListNode l, ListNode r) {
        if ( l == null )
            return r;
        else if ( r == null )
            return l;
        else if ( l.val < r.val ) {
            l.next = merge(l.next, r);
            return l;
        } else {
            r.next = merge(r.next, l);
            return r;
        }
    }

    private static int len(ListNode n) {
        return n != null ? (len(n.next) + 1) : 0;
    }

}
